package sort;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) throws Exception {
        int total = 1000000;
        int[] list = new int[total];
        int temp[] = new int[total];
        for (int i = 0; i < total; i++) {
            int rand = (int) (Math.random() * total);
            list[i] = rand;
        }

        long startTime = System.currentTimeMillis();
        quickSort(list, 0, list.length - 1);
        long end = System.currentTimeMillis();
        System.out.println(end - startTime);
        //printList(list);
    }

     private static void quickSort(int[] target, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = target[left];// 基准点
        int lo = left;
        int hi = right;
        while (lo < hi) {

            while (target[hi] >= pivot && lo < hi) {
                hi--;
            }
            //把右边受阴元素和左边换
            target[lo] = target[hi];

            while (target[lo] <= pivot && lo < hi) {
                lo++;
            }
            //把左边受阴元素和右边换
            target[hi] = target[lo];
        }
        //把拿出来的元素放回去
        target[lo] = pivot;

        quickSort(target, left, lo - 1);
        quickSort(target, lo + 1, right);
    }

    private static void printList(int[] list) {
        for (int i1 : list) {
            System.out.print(i1 + ",");
        }
        System.out.println();
    }
}
